//有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请
//编写代码计算叠罗汉最多能叠几个人。 
//
// 示例： 
//
// 
//输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
//输出：6
//解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190) 
//
//
// 提示： 
//
// 
// height.length == weight.length <= 10000 
// 
//
// Related Topics 数组 二分查找 动态规划 排序 👍 117 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-09-14 23:22:46
 * @description 面试题 17.08.马戏团人塔
 */
public class CircusTowerLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CircusTowerLcci fun=new CircusTowerLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int bestSeqAtIndex1(int[] height, int[] weight) {
		int n = height.length;
		if(n < 2) return n;
		int[][] arr = new int[n][2];
		for(int i = 0; i < n; ++i){
			arr[i][0] = height[i];
			arr[i][1] = weight[i];
		}
		// 对身高进行排序，对于身高相同的，对体重进行降序
		Arrays.sort(arr,(o1, o2) -> o1[0] - o2[0] == 0 ? o2[1] - o1[1] : o1[0] - o2[0]);

		// 转为利用 二分法 求 上升子序列 问题
		List<Integer> list = new ArrayList<>();
		list.add(arr[0][1]);

		for(int i = 1; i < n; ++i){
			int num = arr[i][1];
			// 因为身高递增，所以只需要考虑体重，如果体重满足，直接加入
			if(num > list.get(list.size() - 1)) list.add(num);
			else{
				// 二分查找，找到第一个大于等于num的索引
				// 如果找到的索引等于list.size()，则说明num比所有元素都大，直接加入
				// 否则，将num替换掉list中索引为index的元素
				//为什么要把num替换掉list中索引为index的元素？
				//而不是只替换末尾的元素？
				//替换操作不会减少当前的最长序列长度
				//但会让后续更容易扩展序列（因为结尾值更小）
				//这保证了我们最终找到的是真正的最长可能序列
				//
				int index = binarySearch(list,num);
				list.set(index,num);
			}
		}
		return list.size();
	}
	int binarySearch(List<Integer> arr,int target){
		int l = 0,r = arr.size();
		while(l < r){
			int mid = (r - l) / 2 + l;
			if(arr.get(mid) < target) l = mid + 1;
			else r = mid;
		}
		return l;
	}
	public int bestSeqAtIndex(int[] height, int[] weight) {
		int len = height.length;
		int[][] person = new int[len][2];
		for (int i = 0; i < len; ++i)
			person[i] = new int[]{height[i], weight[i]};
		Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		int[] dp = new int[len];
		int res = 0;
		for (int[] pair : person) {
			int i = Arrays.binarySearch(dp, 0, res, pair[1]);
			if (i < 0)
				i = -(i + 1);
			dp[i] = pair[1];
			if (i == res)
				++res;
		}
		return res;
	}
	// 动态规划超时超内存
	private int[][] person, memo;
	private int len;

	public int bestSeqAtIndex2(int[] height, int[] weight) {
		len = height.length;
		person = new int[len][2];
		for (int i = 0; i < len; ++i)
			person[i] = new int[]{height[i], weight[i]};

		Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		memo = new int[len + 1][len];
		for (int[] l : memo)
			Arrays.fill(l, -1);
		return dfs(-1, 0, 0);
	}

	private int dfs(int pre_idx, int cur_idx, int weight_bound) {
		if (cur_idx == len)
			return 0;

		if (memo[pre_idx + 1][cur_idx] >= 0)
			return memo[pre_idx + 1][cur_idx];

		int taken = 0;
		if (pre_idx < 0 || person[cur_idx][1] > weight_bound)
			taken = 1 + dfs(cur_idx, cur_idx + 1, person[cur_idx][1]);
		int not_taken = dfs(pre_idx, cur_idx + 1, weight_bound);
		return memo[pre_idx + 1][cur_idx] = Math.max(taken, not_taken);
	}
	// 动态规划超时
	public int bestSeqAtIndex3(int[] height, int[] weight) {
		int len = height.length;
		int[][] person = new int[len][2];
		for (int i = 0; i < len; ++i)
			person[i] = new int[]{height[i], weight[i]};

		Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		int[] dp = new int[len];
		dp[0] = 1;
		int res = 1;
		for (int i = 1; i < len; ++i) {
			int max_val = 0, base_weight = person[i][1];
			for (int j = 0; j < i; ++j)
				if (base_weight > person[j][1])
					max_val = Math.max(max_val, dp[j]);
			dp[i] = max_val + 1;
			res = Math.max(res, dp[i]);
		}
		return res;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
